//
//  HeapStruct.c
//  AlgorithmLearning
//
//  Created by aron on 2017/11/2.
//  Copyright © 2017年 aron. All rights reserved.
//

#include "HeapStruct.h"
#include <stdlib.h>
#include <err.h>
#include <math.h>


#define MinPQSize   10
#define MinData     0

PriorityQueue PQ_Initialize(int MaxElements) {
    PriorityQueue H = NULL;
    if (MaxElements < MinPQSize) {
        err(1, "队列长度小于最小值10");
    }
    H = malloc(sizeof(struct HeapStruct));
    if (NULL == H) {
        err(1, "Out of space");
    }
    H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
    if (NULL == H->Elements) {
        err(1, "Out of space");
    }
    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;
    return H;
}

void PQ_InsertToMinQueue(ElementType x,PriorityQueue H) {
    if (PQ_IsFull(H)) {
        err(1, "队列满，不可插入数据");
    }
    // 最小堆，上虑操作
    int i;
    for (i = ++H->Size; H->Elements[i/2] > x; i /= 2) {
        H->Elements[i] = H->Elements[i/2];
    }
    H->Elements[i] = x;
}

ElementType PQ_DeleteMin(PriorityQueue H) {
    if (PQ_IsEmpty(H)) {
        err(1, "Empty");
    }

    ElementType MinElem = H->Elements[1];
    
    // 最小堆，最后一个元素放在顶部，下虑操作
    ElementType lastElement = H->Elements[H->Size--];
    
    int i;
    int child;
    for (i = 1; i * 2<=H->Size; i=child) {
        // 找到孩子节点中小的往上移动
        child = i * 2;
        if (child+1 <= H->Size && H->Elements[child+1] < H->Elements[child] ) {
            child += 1;
        }
        if (child <= H->Size && H->Elements[child] < lastElement) {
            H->Elements[i] = H->Elements[child];
        } else {
            break;
        }
    }
    
    // 放到指定位置
    H->Elements[i] = lastElement;
    
    // 最小元素放在最后，
    // 使用堆排序的时候不用增加额外的空间保存排序后的数据，排序后的数据是倒叙的
    H->Elements[H->Size+1] = MinElem;
    
    return MinElem;
}

ElementType PQ_FindMin(PriorityQueue H) {
    if (PQ_IsEmpty(H)) {
        err(1, "空队列");
    }
    return H->Elements[1];
}

void PQ_InsertToMaxQueue(ElementType x,PriorityQueue H) {
    if (PQ_IsFull(H)) {
        err(1, "队列满，不可插入数据");
    }
    // 最大堆，上虑操作
    int i;
    for (i = ++H->Size; H->Elements[i/2] < x && i > 0; i /= 2) {
        H->Elements[i] = H->Elements[i/2];
    }
    H->Elements[i] = x;
}

ElementType PQ_DeleteMax(PriorityQueue H) {
    if (PQ_IsEmpty(H)) {
        err(1, "Empty");
    }
    ElementType MaxElement = H->Elements[1];
    ElementType LastElement = H->Elements[H->Size--];
    
    // 寻找子节点中大的值，交换
    int childIndex = 1;
    int i;
    for (i = 1; (i * 2)<= H->Size; i = childIndex) {
        // 更新父节点
        childIndex = i * 2;
        if (childIndex + 1 <= H->Size && H->Elements[childIndex + 1] > H->Elements[childIndex]) {
            childIndex = childIndex+1;
        }
        
        // childIndex <= H->Size !!
        if (childIndex <= H->Size && H->Elements[childIndex] > LastElement) {
            H->Elements[i] = H->Elements[childIndex];
        } else {
            break;
        }
    }
    
    // 这里需要使用i,如果使用childIndex会遇到
    // if (childIndex <= H->Size && H->Elements[childIndex] > LastElement) 判断为false,childIndex越界
    H->Elements[i] = LastElement;
    
    return MaxElement;
}

ElementType PQ_FindMax(PriorityQueue H) {
    if (PQ_IsEmpty(H)) {
        err(1, "空队列");
    }
    return H->Elements[1];
}

int PQ_IsFull(PriorityQueue H) {
    return H->Size >= H->Capacity;
}

int PQ_IsEmpty(PriorityQueue H) {
    return H->Size == 0;
}



